package offer2

import "sort"

/**
原题链接:
https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/

剑指offer 38.字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
*/

func goodsOrder(goods string) []string {
	byteArr := []byte(goods)
	sort.Slice(byteArr, func(i, j int) bool { return byteArr[i] < byteArr[j] })

	n := len(byteArr)
	res := make([]string, 0)
	path := make([]byte, 0, n)
	used := make([]bool, n)
	var dfs func(int)
	dfs = func(cur int) {
		if cur == n {
			res = append(res, string(path))
			return
		}
		for i := 0; i < len(byteArr); i++ {
			if i > 0 && !used[i-1] && byteArr[i-1] == byteArr[i] || used[i] { //i > 0 如果当前位置和i-1位置元素相同, 并且i-1已经被使用过了 || user[i]本身就被使用了
				continue
			}
			used[i] = true
			path = append(path, byteArr[i])
			dfs(cur + 1)
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs(0)
	return res
}
